package ch.ethz.fcl.metrobuzz.algorithm.network.shortest_path.general;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

import ch.ethz.fcl.metrobuzz.algorithm.network.Path;
import ch.ethz.fcl.metrobuzz.data.MBData;
import ch.ethz.fcl.metrobuzz.data.accessibility.cost.MBEdgeCost;
import ch.ethz.fcl.metrobuzz.data.scene.basemap.Edge;
import ch.ethz.fcl.metrobuzz.data.scene.basemap.Node;

/**
 * Dijkstra algorithm implemented for find all paths from one node to all other
 * nodes
 * 
 * @author Zeng Wei
 * @email zeng@arch.ethz.ch
 * 
 */
public class OneToAllDijkstra {
	private MBData data;
	// record the visiting nodes
	private List<Node> visitingNodes;
	private List<Node> visitedNodes;
	// records path from source to all nodes
	private Map<Node, Path> pathMap;

	public OneToAllDijkstra(MBData data) {
		this.data = data;
	}

	/**
	 * @param source
	 * @return the shortest path from a node to all other nodes at current time
	 */
	public LinkedHashMap<Node, Path> getShortestPath(Node source) {
		pathMap = new HashMap<Node, Path>();
		// sort paths according to the cost
		LinkedHashMap<Node, Path> sortedPathMap = new LinkedHashMap<Node, Path>();

		visitedNodes = new ArrayList<Node>();

		visitingNodes = new ArrayList<Node>();
		visitingNodes.add(source);

		Path path = new Path();
		path.addPath(source, 0);
		pathMap.put(source, path);

		while (visitingNodes.size() != 0) {
			Node evaluationNode = getNodeWithLowestDistance(pathMap);
			visitingNodes.remove(evaluationNode);
			visitedNodes.add(evaluationNode);
			// put into the sorted path so the cost always increase
			sortedPathMap.put(evaluationNode, pathMap.get(evaluationNode));
			evaluatedNeighbors(evaluationNode);
		}

		return sortedPathMap;
	}

	// find node with the lowest distance in visitingNode and return it
	private Node getNodeWithLowestDistance(Map<Node, Path> pathMap) {
		float minDistance = Float.MAX_VALUE;
		Node lowestDistanceNode = visitingNodes.get(0);
		for (Node node : visitingNodes) {
			Path path = pathMap.get(node);
			float cost = path.getCost();
			if (cost <= minDistance) {
				minDistance = cost;
				lowestDistanceNode = node;
			}
		}
		return lowestDistanceNode;
	}

	private void evaluatedNeighbors(Node evaluationNode) {
		List<Integer> edgeIndexes = data.getRoadNetwork().getStartEdgeIndex(
				evaluationNode);
		if (edgeIndexes == null || edgeIndexes.size() == 0) {
			return;
		}
		for (Integer edgeIndex : edgeIndexes) {
			Edge edge = data.getRoadNetwork().getPassingEdges().get(edgeIndex);
			Node endNode = edge.getEndNode();

			// default edge cost is its distance
			float edgeCost = edge.distance();
			
			// only for the nodes not visited yet
			if (!visitedNodes.contains(endNode)) {
				if (data.getCost() != null) {
					MBEdgeCost roadCost = data.getCost().getEdgeCost(edge);
					if (roadCost == null)
						continue;
					edgeCost = roadCost.getCost(MBData.startTime);
				}

				Path comingPath = pathMap.get(evaluationNode);
				Path nextPath = pathMap.get(endNode);

				// path to the end node is not exist or the cost is bigger than
				// new path
				if (nextPath == null
						|| (nextPath.getCost() > comingPath.getCost()
								+ edgeCost)) {
					// create a new path for the node
					Path newPath = new Path();

					List<Node> nodes = comingPath.getPath();
					for (int i = 0; i < nodes.size(); i++) {
						if (i == 0)
							newPath.addPath(nodes.get(0), 0);
						if (i > 0) {
							Node thisNode = nodes.get(i);
							Node preNode = nodes.get(i - 1);
							for (Edge e : preNode.getOutEdges())
								if (e.getEndNode().getId()
										.equals(thisNode.getId())) {

									float newCost = e.distance();
									if (data.getCost() != null) {
										MBEdgeCost newRoadCost = data.getCost()
												.getEdgeCost(e);

										if (newRoadCost == null)
											continue;

										newCost = newRoadCost
												.getCost(MBData.startTime);
									}

									newPath.addPath(thisNode, newCost);
									break;
								}
						}
					}

					// for (Edge e : comingPath.getPath())
					// newPath.addEdge(e);
					// newPath.addEdge(edge);
					newPath.addPath(endNode, edgeCost);

					if (nextPath != null)
						// if path already exist,remove it
						pathMap.remove(endNode);
					else
						// if path not exist, add node to visitingNodes
						visitingNodes.add(endNode);

					pathMap.put(endNode, newPath);
				}
			}
		}
	}
}
